package com.atguigu.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: shenhao
 * @CreatTime: 2024/11/26 11:36
 * @Version: 1.0 sync compute
 */
// 给定一组单词，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他两个单词组合而成，这两个单词的组合顺序是索引值小的在左，
// 索引值大的在右。若有多个长度相同的结果，返回其中索引最大的一项，若没有符合要求的单词则返回空字符串。

// 示例：
// 输入：["ac","ad","acad","aga","agaacad","sk","skacad"，"hasdjasnskss"]
// 结果：agaacad
// 示例2
// 输入：["ac","ad","acad","aga","agaacad","skd","skdacad","hasdjasnskss"]
// 结果：skdacad
// constraint
public class Main {
    public static void main(String[] args) {
        String[] array1 = {"ac", "ad", "acad", "aga", "agaacad", "sk", "skacad", "hasdjasnskss"};
        String[] array2 = {"ac", "ad", "acad", "aga", "agaacad", "skd", "skdacad", "hasdjasnskss"};
        System.out.println(Main.func(array1));
        System.out.println(Main.func(array2));
    }

    //**以上代码不要修改，不要修改方法名称

    public static String func(String[] array) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i], i);
        }
        String result = "";
        int maxLength = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i].length() < maxLength) continue;
            //遍历拆分单词
            for (int j = 0; j < array[i].length(); j++) {
                String prefix = array[i].substring(0, j);
                String suffix = array[i].substring(j);
                //获取对应下标
                if (map.containsKey(prefix) && map.containsKey(suffix)) {
                    int prefixIndex = map.get(prefix);
                    int suffixIndex = map.get(suffix);

                    if (prefixIndex < i && suffixIndex < i && prefixIndex > suffixIndex) {
                        if (array[i].length() >= maxLength ) {
                            maxLength = array[i].length();
                            result = array[i];
                        }
                    }
                }
            }
        }
        return result;
    }
}
